Technical Field
The present invention relates to a distributed database formed by a plurality of computers.
Background Art
In recent years, the amount of data has increased rapidly in a computer system which executes applications using a Web and various systems have been known which distribute data to a plurality of servers and improve a data access performance. For example, in a relational database management system (RDBMS), a method has been known which separates data into predetermined ranges (for example, key ranges) and distributes the separated data to a plurality of servers, thereby improving the access performance of the entire system.
In addition, a Not only SQL (NoSQL) database, such as a key value store (KVS), has been known as a system used in, for example, a cache server. The KVS stores a plurality of records each having a pair of data (value) and a data identifier (key).
The KVS has various structures, such as a structure (memory storage) in which data is stored in a volatile recording medium that can access data at a high speed, for example, a memory, a structure (disk storage) in which data is stored in a non-volatile recording medium having a high data storage permanence, for example, a solid state disk (SSD) or an HDD, and a combination of the structures.
In an in-memory KVS, a data access speed is higher than that in a disk-type KVS. However, the in-memory KVS has some defects. First, the in-memory KVS has a lower memory capacity which can be mounted in one server than the SSD or the HDD due to, for example, physical restrictions and stores a smaller amount of data than the disk-type KVS. Second, since the memory is a volatile recording medium, data in the memory is erased when the server is stopped due to any failure.
An example of the system which overcomes the defects is an in-memory distributed KVS (hereinafter, referred to as a distributed KVS). A plurality of servers are separated into clusters and the distributed KVS is formed on a memory of the server included in the cluster. For the first defect, the memories of a plurality of servers are integrated to ensure memory capacity which cannot be obtained by one server. For the second defect, the same data is copied between a plurality of servers to prevent data from being erased even when some of the servers are stopped.
Each server which form the distributed KVS takes charge of a range which does not overlap the ranges of other servers and stores an aggregate (hereinafter, referred to as a partition) of data included in the range. In addition, each server stores copies of the partitions which are managed by other servers.
A special server, such as a management server, is not present or is multiplexed in the distributed KVS. Therefore, a single point of failure does not occur in the distributed KVS. That is, even when a failure occurs in an arbitrary server, it is possible to continuously perform a process on the basis of the partitions copied by other servers and the computer system is not stopped. Therefore, the distributed KVS also has fault-tolerance.
When the amount of data stored in the distributed KVS increases, a load applied to the server increases or a data storage space is reduce. As one of the measures for solving the problems, there is a scale-out system in which a new server is added to a cluster. In the scale-out system, a process (hereinafter, referred to as a rebalancing process) that changes the range which the server takes charge of is performed. In addition, when data is distributed only to some of the servers, the throughput of the system is reduced. As one of measures for solving the problem, the rebalancing process is performed to solve the data unbalance problem.
A technique related to the above-mentioned rebalancing process is disclosed in Patent Document 1.
Patent Document 1 discloses a technique in which a process of preparing a new partition after rebalancing for the existing range and the existing partition corresponding to the existing range, copying data from the existing partition to the new partition, and switching access from the existing range and the existing partition corresponding to the existing range to the new range and the new partition corresponding to the new range after the copying of data is completed is performed to achieve the rebalancing process.